/*
  常见前端面试算法与工具函数合集
  - 数组转树 (arrayToTree)
  - 多维数组拍平 (flattenArray)
  - 深拷贝 (deepClone)
  - 深比较 (deepEqual)
  - 树的 DFS/BFS 遍历 (dfsTraverseTree / bfsTraverseTree)
  - 二分查找 (binarySearch)
  - 排序：快速排序/归并排序/冒泡排序 (quickSort / mergeSort / bubbleSort)
  - 滑动窗口：最长无重复子串/最短子数组长度 (lengthOfLongestSubstring / minSubArrayLen)
  - 链表：反转链表 (reverseList)
  - 数组/哈希：两数之和 (twoSum)
  - LRU 缓存 (LRUCache)
  - 函数工具：防抖/节流/柯里化/组合 (debounce / throttle / curry / compose)
  - Promise 工具：all / allSettled / any / race (promiseAll / promiseAllSettled / promiseAny / promiseRace)
  - 事件总线 (EventEmitter)
  - 并发调度器 (pLimit)
  - 树遍历：前序/中序/后序 (preorder / inorder / postorder)
  - 拓扑排序 (topologicalSort)
  - 去重/分组/洗牌 (uniqueArray / groupBy / shuffle)
*/

// =============== 数组转树 =================
/*
  步骤说明：
  1) 读取配置项（id、parentId、children 字段名与根父ID）。
  2) 第一次遍历：为每个元素创建节点副本，并建立 id -> 节点 的映射。
  3) 第二次遍历：根据 parentId 将节点插入到其父节点的 children 中。
  4) 若 parentId 等于根父ID或未找到父节点，则视为根节点放到 roots。
  5) 返回 roots 作为树的根列表。
*/
function arrayToTree(list, options) { // 将平铺数组转换为树形结构
  options = options || {}; // 确保 options 存在
  var idKey = options.idKey || 'id'; // id 字段名
  var parentIdKey = options.parentIdKey || 'parentId'; // 父 id 字段名
  var childrenKey = options.childrenKey || 'children'; // 子节点字段名
  var rootParentId = typeof options.rootParentId === 'undefined' ? null : options.rootParentId; // 根父ID
  var idToNode = {}; // 使用普通对象作为 id 到节点的映射
  var roots = []; // 存放根节点的数组
  for (var i = 0; i < list.length; i++) { // 遍历输入数组，第一遍构建映射
    var item = list[i]; // 当前元素
    var node = {}; // 为当前元素创建一个新对象
    for (var k in item) { // 将原属性拷贝到新对象
      if (Object.prototype.hasOwnProperty.call(item, k)) { // 仅拷贝自有属性
        node[k] = item[k]; // 赋值拷贝
      }
    }
    node[childrenKey] = []; // 初始化 children 数组
    idToNode[item[idKey]] = node; // 建立 id 到节点的映射
  }
  for (var j = 0; j < list.length; j++) { // 第二遍根据 parentId 构建层级
    var cur = list[j]; // 当前元素
    var curNode = idToNode[cur[idKey]]; // 找到对应的新节点
    var pid = cur[parentIdKey]; // 读取父ID
    if (pid === rootParentId || !idToNode[pid]) { // 若为根或找不到父节点
      roots.push(curNode); // 放入根集合
    } else { // 否则有父节点
      idToNode[pid][childrenKey].push(curNode); // 将当前节点放入父节点 children
    }
  }
  return roots; // 返回根节点数组
}

// =============== 多维数组拍平 =================
/*
  步骤说明：
  1) 边界处理：非数组或拍平深度<=0 时直接返回浅拷贝。
  2) 使用显式栈保存待处理项与其当前层级 level。
  3) 出栈：若为数组且尚未达到深度，逆序入栈其子元素并 level+1。
  4) 否则压入结果数组 result。
  5) 由于采用栈的后进先出，最终 reverse 以恢复原有顺序。
*/
function flattenArray(array, depth) { // 将多维数组拍平到指定深度
  if (typeof depth === 'undefined') depth = Infinity; // 默认无限深度
  if (!Array.isArray(array) || depth <= 0) return array.slice(0); // 边界：非数组或深度<=0 返回浅拷贝
  var result = []; // 存放拍平后的结果
  var stack = []; // 栈存放待处理项
  for (var i = array.length - 1; i >= 0; i--) { // 逆序入栈保持顺序
    stack.push({ value: array[i], level: 0 }); // 入栈值与当前层级
  }
  while (stack.length) { // 栈不空循环
    var item = stack.pop(); // 取出栈顶
    var value = item.value; // 当前值
    var level = item.level; // 当前层级
    if (Array.isArray(value) && level < depth) { // 若是数组且未超过深度
      for (var j = value.length - 1; j >= 0; j--) { // 逆序压入子元素
        stack.push({ value: value[j], level: level + 1 }); // 子元素层级+1
      }
    } else { // 非数组或超过深度
      result.push(value); // 直接放入结果
    }
  }
  return result; // 返回结果（顺序已保持）
}

// =============== 深拷贝 =================
/*
  步骤说明：
  1) 原始值或 null 直接返回；循环引用通过 WeakMap 记忆化处理。
  2) 内建对象特判：Date/RegExp 分别克隆；（为简单起见忽略 Map/Set 原生结构）。
  3) 普通对象/数组：仅拷贝可枚举自有属性（使用 Object.keys 与 for 循环）。
*/
function deepClone(source, weakMap) { // 进行深拷贝
  if (typeof weakMap === 'undefined') weakMap = new WeakMap(); // 默认创建缓存表
  if (source === null || typeof source !== 'object') return source; // 原始值与 null 直接返回
  if (weakMap.has(source)) return weakMap.get(source); // 处理循环引用
  if (source instanceof Date) return new Date(source.getTime()); // Date 克隆
  if (source instanceof RegExp) return new RegExp(source.source, source.flags); // RegExp 克隆
  var target = Array.isArray(source) ? [] : {}; // 目标对象：数组或普通对象
  weakMap.set(source, target); // 先缓存，避免递归时循环引用
  var keys = Object.keys(source); // 仅获取可枚举自有属性键
  for (var i = 0; i < keys.length; i++) { // 遍历键
    var key = keys[i]; // 当前键
    target[key] = deepClone(source[key], weakMap); // 递归拷贝子属性
  }
  return target; // 返回拷贝结果
}

// =============== 深比较 =================
/*
  步骤说明：
  1) 使用 Object.is 处理 NaN 等边界；先比类型与 null。
  2) 处理循环结构：seen 记录已比较映射以避免无限递归。
  3) 内建对象特判：Date/RegExp 分别等价性比较。（简化：不处理 Map/Set）。
  4) 使用 Object.keys 比较自有可枚举键集合与对应值的递归相等。
*/
function deepEqual(a, b, seen) { // 深度比较两个值是否“结构相等”
  if (typeof seen === 'undefined') seen = new WeakMap(); // 默认记录表
  if (Object.is(a, b)) return true; // 严格相同直接返回 true
  if (typeof a !== typeof b) return false; // 类型不同不相等
  if (a === null || b === null) return a === b; // 处理 null 情况
  if (typeof a !== 'object') return a === b; // 原始类型直接比较
  if (seen.get(a) === b) return true; // 循环结构短路
  seen.set(a, b); // 记录已比较的映射
  if (a instanceof Date && b instanceof Date) return a.getTime() === b.getTime(); // Date 比较时间戳
  if (a instanceof RegExp && b instanceof RegExp) return a.source === b.source && a.flags === b.flags; // RegExp 比较源与标志
  var aKeys = Object.keys(a); // a 的自有可枚举键
  var bKeys = Object.keys(b); // b 的自有可枚举键
  if (aKeys.length !== bKeys.length) return false; // 键数量不同不相等
  for (var i = 0; i < aKeys.length; i++) { // 遍历每个键
    var key = aKeys[i]; // 当前键
    if (bKeys.indexOf(key) === -1) return false; // b 不包含该键
    if (!deepEqual(a[key], b[key], seen)) return false; // 递归比较对应的值
  }
  return true; // 所有键与值均相等
}

// =============== 树的遍历 =================
/*
  DFS 步骤说明：
  1) 将根节点逆序入栈，保证同层从左到右访问顺序。
  2) 循环弹栈访问节点，随后将其 children 逆序入栈。
  3) 栈空结束。
*/
function dfsTraverseTree(roots, childrenKey, visit) { // 深度优先遍历树
  if (typeof childrenKey === 'undefined') childrenKey = 'children'; // 默认 children 键
  if (typeof visit !== 'function') visit = function () {}; // 默认空函数
  if (!Array.isArray(roots)) return; // 非数组直接返回
  var stack = []; // 初始化栈
  for (var i = roots.length - 1; i >= 0; i--) { // 逆序压入根
    stack.push(roots[i]); // 入栈根节点
  }
  while (stack.length) { // 栈不空循环
    var node = stack.pop(); // 弹出一个节点
    visit(node); // 访问当前节点
    var children = node && node[childrenKey]; // 读取子节点数组
    if (Array.isArray(children) && children.length) { // 若有子节点
      for (var j = children.length - 1; j >= 0; j--) { // 逆序压栈
        stack.push(children[j]); // 将子节点入栈
      }
    }
  }
}

/*
  BFS 步骤说明：
  1) 将根节点入队。
  2) 循环出队访问节点，将其 children 入队。
  3) 队列为空结束。
*/
function bfsTraverseTree(roots, childrenKey, visit) { // 广度优先遍历树
  if (typeof childrenKey === 'undefined') childrenKey = 'children'; // 默认 children 键
  if (typeof visit !== 'function') visit = function () {}; // 默认空函数
  if (!Array.isArray(roots)) return; // 非数组直接返回
  var queue = []; // 初始化队列
  for (var i = 0; i < roots.length; i++) { // 将所有根节点入队
    queue.push(roots[i]); // 入队根节点
  }
  while (queue.length) { // 队列不空循环
    var node = queue.shift(); // 出队一个节点
    visit(node); // 访问当前节点
    var children = node && node[childrenKey]; // 读取子节点数组
    if (Array.isArray(children) && children.length) { // 若有子节点
      for (var j = 0; j < children.length; j++) { // 依次入队
        queue.push(children[j]); // 将子节点入队
      }
    }
  }
}

// =============== 二分查找（有序升序数组） =================
/*
  步骤说明：
  1) 设定左右边界 left/right。
  2) 取中点 mid，比较值与目标 target。
  3) 根据大小调整左右边界，直至找到或区间为空。
*/
function binarySearch(sortedArray, target) { // 在升序数组中查找目标值的下标
  var left = 0; // 左边界
  var right = sortedArray.length - 1; // 右边界
  while (left <= right) { // 只要区间有效就继续
    var mid = Math.floor((left + right) / 2); // 取中点（最简单写法）
    var val = sortedArray[mid]; // 读取中点值
    if (val === target) return mid; // 找到直接返回
    if (val < target) { // 若中点值小于目标
      left = mid + 1; // 舍弃左半部分
    } else { // 否则中点值大于目标
      right = mid - 1; // 舍弃右半部分
    }
  }
  return -1; // 未找到返回 -1
}

// =============== 排序 =================
/*
  快速排序步骤说明：
  1) 选取中点作为基准 pivot 并移出。
  2) 遍历数组小于 pivot 放左侧，否则放右侧。
  3) 递归排序左右子数组并合并。
*/
function quickSort(arr) { // 快速排序，返回新数组
  if (arr.length <= 1) return arr.slice(0); // 长度 0/1 返回拷贝
  var list = arr.slice(0); // 复制一份工作数组
  var midIndex = Math.floor(list.length / 2); // 中间索引
  var pivot = list.splice(midIndex, 1)[0]; // 取出基准值
  var left = []; // 小于 pivot 的元素
  var right = []; // 大于等于 pivot 的元素
  for (var i = 0; i < list.length; i++) { // 遍历剩余元素
    var n = list[i]; // 当前值
    if (n < pivot) { // 比较与 pivot 大小
      left.push(n); // 放入左侧
    } else { // 否则放右侧
      right.push(n); // 放入右侧
    }
  }
  var sortedLeft = quickSort(left); // 递归排序左侧
  var sortedRight = quickSort(right); // 递归排序右侧
  return sortedLeft.concat([pivot], sortedRight); // 合并返回
}

/*
  归并排序步骤说明：
  1) 二分数组直至长度为 1。
  2) 归并两个有序子数组，按小到大输出到新数组。
  3) 返回合并结果。
*/
function mergeSort(arr) { // 归并排序，返回新数组
  if (arr.length <= 1) return arr.slice(0); // 长度 0/1 返回拷贝
  var mid = Math.floor(arr.length / 2); // 中间索引
  var leftPart = arr.slice(0, mid); // 左半部分
  var rightPart = arr.slice(mid); // 右半部分
  var left = mergeSort(leftPart); // 递归排序左半
  var right = mergeSort(rightPart); // 递归排序右半
  var result = []; // 存放合并后的结果
  var i = 0; // 左指针
  var j = 0; // 右指针
  while (i < left.length && j < right.length) { // 两边都还有元素
    if (left[i] <= right[j]) { // 左边更小
      result.push(left[i]); // 放入结果
      i++; // 左指针右移
    } else { // 右边更小
      result.push(right[j]); // 放入结果
      j++; // 右指针右移
    }
  }
  while (i < left.length) { // 剩余左侧元素
    result.push(left[i]); // 依次放入
    i++; // 左指针右移
  }
  while (j < right.length) { // 剩余右侧元素
    result.push(right[j]); // 依次放入
    j++; // 右指针右移
  }
  return result; // 返回合并后的有序结果
}

/*
  冒泡排序步骤说明：
  1) 外层遍历控制趟数，内层相邻元素两两比较并交换。
  2) 若一趟无交换则提前结束。
*/
function bubbleSort(arr) { // 冒泡排序，返回新数组
  var a = arr.slice(0); // 拷贝输入，避免修改原数组
  for (var i = 0; i < a.length - 1; i++) { // 外层控制趟数
    var swapped = false; // 标记本趟是否发生交换
    for (var j = 0; j < a.length - 1 - i; j++) { // 内层比较与交换
      if (a[j] > a[j + 1]) { // 若前一个比后一个大
        var t = a[j]; // 暂存 a[j]
        a[j] = a[j + 1]; // 交换位置
        a[j + 1] = t; // 放回暂存
        swapped = true; // 标记发生交换
      }
    }
    if (!swapped) break; // 若本趟无交换则提前结束
  }
  return a; // 返回排序后的数组副本
}

// =============== 滑动窗口 =================
/*
  最长无重复子串步骤说明：
  1) 维护窗口 [left,right] 与字符最近出现位置表 lastIndex。
  2) 扩右指针；若重复且位置在窗口内，则移动 left 到重复字符后。
  3) 持续更新最大长度。
*/
function lengthOfLongestSubstring(s) { // 计算最长无重复子串长度
  var left = 0; // 窗口左边界
  var lastIndex = {}; // 字符 -> 最近出现的下标
  var maxLen = 0; // 记录最大长度
  for (var right = 0; right < s.length; right++) { // 右指针扩展窗口
    var ch = s.charAt(right); // 当前字符
    var exist = Object.prototype.hasOwnProperty.call(lastIndex, ch); // 是否出现过
    if (exist && lastIndex[ch] >= left) { // 若在窗口内重复
      left = lastIndex[ch] + 1; // 移动左边界到重复位置后一位
    }
    lastIndex[ch] = right; // 更新当前字符最近出现位置
    var currLen = right - left + 1; // 当前窗口长度
    if (currLen > maxLen) maxLen = currLen; // 更新最大长度
  }
  return maxLen; // 返回结果
}

/*
  最短长度子数组步骤说明：
  1) 维护窗口和 sum，右指针累计。
  2) 当 sum>=target 时收缩左指针并更新最小长度。
  3) 遍历结束输出最小长度，不存在则为 0。
*/
function minSubArrayLen(target, nums) { // 和至少为 target 的最短子数组长度
  var left = 0; // 左指针
  var sum = 0; // 当前窗口和
  var minLen = Infinity; // 最小长度，初始为正无穷
  for (var right = 0; right < nums.length; right++) { // 右指针遍历
    sum += nums[right]; // 扩张窗口：加入右端元素
    while (sum >= target) { // 只要满足条件就收缩左侧
      var len = right - left + 1; // 当前窗口长度
      if (len < minLen) minLen = len; // 更新最小长度
      sum -= nums[left]; // 移除左端元素
      left++; // 左指针右移
    }
  }
  return isFinite(minLen) ? minLen : 0; // 若未更新过则返回 0
}

// =============== 链表 =================
/*
  单链表节点结构：
  - val: 节点值
  - next: 指向下一个节点的指针
*/
class ListNode {
  constructor(val, next = null) {
    this.val = val;
    this.next = next;
  }
}

/*
  反转链表步骤说明：
  1) 使用 prev/curr 指针迭代；暂存 next。
  2) 将 curr.next 指向 prev 完成局部反转。
  3) prev 前进到 curr，curr 前进到 next；循环至结束。
  4) 返回新的头结点 prev。
*/
function reverseList(head) { // 反转单链表
  var prev = null; // 前驱指针，初始为 null
  var curr = head; // 当前指针从头结点开始
  while (curr) { // 遍历链表
    var nextTemp = curr.next; // 暂存下一个节点
    curr.next = prev; // 当前节点的 next 指向前驱，实现反转
    prev = curr; // 前驱前进到当前
    curr = nextTemp; // 当前前进到原来的下一个
  }
  return prev; // prev 指向新的头结点
}

// =============== 两数之和 =================
/*
  步骤说明：
  1) 使用对象（最原生结构）存储 值->下标 映射。
  2) 遍历数组，计算补数 need=target-nums[i]。
  3) 若映射中已有 need（且不是 undefined），返回其下标与当前下标。
  4) 否则记录当前值与当前下标。
*/
function twoSum(nums, target) { // 找出两数之和为 target 的下标
  var indexByValue = {}; // 映射：值 -> 下标
  for (var i = 0; i < nums.length; i++) { // 遍历数组
    var value = nums[i]; // 当前值
    var need = target - value; // 需要的另一个值
    if (Object.prototype.hasOwnProperty.call(indexByValue, need)) { // 若映射中存在 need
      return [indexByValue[need], i]; // 返回两个下标
    }
    indexByValue[value] = i; // 记录当前值及其下标
  }
  return [-1, -1]; // 未找到返回 [-1,-1]
}

// =============== LRU 缓存 =================
/*
  LRU 缓存说明：
  - 使用 Map 维护插入有序性，最近访问元素移动到末尾。
  - put 超出容量时删除 Map 的首个键（最久未使用）。
*/
class LRUCache {
  constructor(capacity) {
    if (!Number.isInteger(capacity) || capacity <= 0) throw new Error('capacity must be positive integer');
    this.capacity = capacity;
    this.map = new Map();
  }
  get(key) {
    if (!this.map.has(key)) return -1;
    const val = this.map.get(key);
    this.map.delete(key);
    this.map.set(key, val);
    return val;
  }
  put(key, value) {
    if (this.map.has(key)) this.map.delete(key);
    this.map.set(key, value);
    if (this.map.size > this.capacity) {
      const lruKey = this.map.keys().next().value;
      this.map.delete(lruKey);
    }
  }
}

// =============== 函数工具 =================
/*
  防抖步骤说明：
  1) 调用时清除上一次定时器。
  2) 立即执行模式：首次无定时器时立刻执行一次。
  3) 否则在 wait 后执行，并在执行后清空定时器引用。
*/
function debounce(fn, wait, immediate = false) {
  let timer = null;
  return function debounced(...args) {
    const context = this;
    if (timer) clearTimeout(timer);
    if (immediate && !timer) fn.apply(context, args);
    timer = setTimeout(() => {
      if (!immediate) fn.apply(context, args);
      timer = null;
    }, wait);
  };
}

/*
  节流步骤说明：
  1) 通过时间戳与定时器控制在 wait 间隔内最多执行一次。
  2) 支持 leading/trailing 配置以控制边缘触发行为。
*/
function throttle(fn, wait, options) {
  const { leading = true, trailing = true } = options || {};
  let lastCallTs = 0;
  let timer = null;
  return function throttled(...args) {
    const context = this;
    const now = Date.now();
    if (!leading && lastCallTs === 0) lastCallTs = now;
    const remaining = wait - (now - lastCallTs);
    if (remaining <= 0) {
      if (timer) { clearTimeout(timer); timer = null; }
      lastCallTs = now;
      fn.apply(context, args);
    } else if (trailing && !timer) {
      timer = setTimeout(() => {
        lastCallTs = leading ? Date.now() : 0;
        timer = null;
        fn.apply(context, args);
      }, remaining);
    }
  };
}

/*
  柯里化说明：
  1) 累积入参；当参数个数达到原函数形参长度时执行。
  2) 否则返回新的函数继续收集参数。
*/
function curry(fn, ...preset) {
  return function curried(...args) {
    const all = preset.concat(args);
    if (all.length >= fn.length) return fn.apply(this, all);
    return curry(fn, ...all);
  };
}

/*
  组合函数说明：
  1) 从右到左依次执行函数，将上一次输出作为下一次输入。
*/
function compose(...fns) {
  return function composed(input) {
    return fns.reduceRight((acc, fn) => fn(acc), input);
  };
}

// =============== Promise 工具 =================
/*
  promiseAll 步骤说明：
  1) 将可迭代对象转为数组，逐个 Promise.resolve 包装。
  2) 按顺序填充结果数组，全部完成后 resolve。
  3) 任一拒绝立即 reject。
*/
function promiseAll(promises) {
  return new Promise((resolve, reject) => {
    const list = Array.from(promises);
    const results = new Array(list.length);
    let completed = 0;
    if (list.length === 0) resolve([]);
    list.forEach((p, i) => {
      Promise.resolve(p).then(val => {
        results[i] = val;
        completed++;
        if (completed === list.length) resolve(results);
      }, reject);
    });
  });
}

/*
  allSettled 说明：
  - 将每个 promise 转换为状态对象 {status,value|reason}，全部完成后返回。
*/
function promiseAllSettled(promises) {
  return Promise.all(Array.from(promises).map(p => Promise.resolve(p)
    .then(value => ({ status: 'fulfilled', value }))
    .catch(reason => ({ status: 'rejected', reason }))));
}

/*
  race 说明：
  - 任意一个 promise 兑现/拒绝后立刻返回该结果。
*/
function promiseRace(promises) {
  return new Promise((resolve, reject) => {
    for (const p of promises) Promise.resolve(p).then(resolve, reject);
  });
}

/*
  any 说明：
  - 任意一个成功即 resolve；全部失败则抛 AggregateError。
*/
function promiseAny(promises) {
  return new Promise((resolve, reject) => {
    const errors = [];
    let rejectedCount = 0;
    const list = Array.from(promises);
    if (list.length === 0) reject(new AggregateError([], 'All promises were rejected'));
    list.forEach((p, i) => {
      Promise.resolve(p).then(resolve, err => {
        errors[i] = err;
        rejectedCount++;
        if (rejectedCount === list.length) reject(new AggregateError(errors, 'All promises were rejected'));
      });
    });
  });
}

// =============== 事件总线 =================
/*
  事件总线说明（最原生实现）：
  - 使用对象保存事件到监听器数组的映射。
  - on: 添加监听；once: 包装一次性监听；off: 移除监听；emit: 触发事件；clear: 清空。
*/
function EventEmitter() { // 构造函数
  this.events = {}; // 事件名 -> 监听器数组
}
EventEmitter.prototype.on = function (event, listener) { // 订阅
  if (!this.events[event]) this.events[event] = []; // 若无该事件数组则初始化
  this.events[event].push(listener); // 添加监听器
  var self = this; // 保存 this 引用
  return function () { self.off(event, listener); }; // 返回取消订阅函数
};
EventEmitter.prototype.once = function (event, listener) { // 一次性订阅
  var self = this; // 保存 this 引用
  function wrapped() { // 包装函数
    self.off(event, wrapped); // 调用后先移除自己
    listener.apply(null, arguments); // 再执行原监听器
  }
  return this.on(event, wrapped); // 以 on 方式注册包装器
};
EventEmitter.prototype.off = function (event, listener) { // 取消订阅
  var arr = this.events[event]; // 取出该事件的监听器数组
  if (!arr) return; // 若不存在直接返回
  for (var i = 0; i < arr.length; i++) { // 遍历查找
    if (arr[i] === listener) { // 找到目标监听
      arr.splice(i, 1); // 从数组中删除
      break; // 结束循环
    }
  }
  if (arr.length === 0) delete this.events[event]; // 若数组空了则删除该事件键
};
EventEmitter.prototype.emit = function (event) { // 触发事件
  var arr = this.events[event]; // 取出监听器数组
  if (!arr || arr.length === 0) return false; // 无监听返回 false
  var args = []; // 收集参数
  for (var i = 1; i < arguments.length; i++) { // 跳过 event 参数
    args.push(arguments[i]); // 收集其余参数
  }
  // 复制一份，避免回调里增删监听影响本次循环
  var listeners = arr.slice(0); // 浅拷贝数组
  for (var j = 0; j < listeners.length; j++) { // 依次调用监听器
    listeners[j].apply(null, args); // 以 null 作为 this 调用
  }
  return true; // 成功触发返回 true
};
EventEmitter.prototype.clear = function () { // 清空所有事件
  this.events = {}; // 重置为新对象
};

// =============== 并发调度器（限制并发量） =================
/*
  并发限制器步骤说明（保留最原生写法）：
  1) 使用数组作为任务队列与数字 activeCount 作为活动计数。
  2) next：若未达上限且队列有任务，则取出并执行；结束后递减并继续调度。
  3) 返回的 limiter(fn) 将任务函数封装为 {fn,resolve,reject} 入队并触发调度。
*/
function pLimit(concurrency) { // 创建并发限制器
  if (!(typeof concurrency === 'number' && concurrency >= 1 && Math.floor(concurrency) === concurrency)) throw new Error('concurrency must be >= 1'); // 基本校验
  var queue = []; // 任务队列
  var activeCount = 0; // 当前执行的任务数量
  function next() { // 调度函数
    if (activeCount >= concurrency) return; // 达到并发上限则返回
    if (queue.length === 0) return; // 队列为空返回
    var item = queue.shift(); // 取出一个任务
    activeCount++; // 活动数+1
    var fn = item.fn; // 任务函数
    var resolve = item.resolve; // 对应的 resolve
    var reject = item.reject; // 对应的 reject
    Promise.resolve().then(fn).then(function (value) { // 执行任务函数
      resolve(value); // 成功时解析
    }, function (err) { // 失败时拒绝
      reject(err); // 拒绝错误
    }).then(function () { // 无论成功失败都在后续进行
      activeCount--; // 活动数-1
      next(); // 继续调度下一个
    });
  }
  return function limiter(fn) { // 返回限制器函数
    return new Promise(function (resolve, reject) { // 返回一个 Promise
      queue.push({ fn: fn, resolve: resolve, reject: reject }); // 将任务入队
      next(); // 触发调度
    });
  };
}

// =============== 二叉树遍历（基于节点 {val,left,right}） =================
/*
  二叉树前序遍历：根 -> 左 -> 右，使用手动栈模拟递归。
*/
function preorder(root, visit = () => {}) {
  const stack = [];
  let node = root;
  while (node || stack.length) {
    while (node) {
      visit(node);
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    node = node.right;
  }
}

/*
  二叉树中序遍历：左 -> 根 -> 右，使用手动栈模拟递归。
*/
function inorder(root, visit = () => {}) {
  const stack = [];
  let node = root;
  while (node || stack.length) {
    while (node) {
      stack.push(node);
      node = node.left;
    }
    node = stack.pop();
    visit(node);
    node = node.right;
  }
}

/*
  二叉树后序遍历：左 -> 右 -> 根，记录 lastVisited 辅助判断回溯方向。
*/
function postorder(root, visit = () => {}) {
  const stack = [];
  let lastVisited = null;
  let node = root;
  while (node || stack.length) {
    if (node) {
      stack.push(node);
      node = node.left;
    } else {
      const peek = stack[stack.length - 1];
      if (peek.right && lastVisited !== peek.right) {
        node = peek.right;
      } else {
        visit(peek);
        lastVisited = stack.pop();
      }
    }
  }
}

// =============== 拓扑排序（Kahn 算法） =================
/*
  步骤说明：
  1) 统计入度 indegree 并构建邻接表 adj。
  2) 将入度为 0 的顶点入队。
  3) 出队顶点并减少其邻接点入度，为 0 则入队。
  4) 遍历结束：若输出数量少于顶点数，说明存在环。
*/
function topologicalSort(vertices, edges) {
  const indegree = new Map(vertices.map(v => [v, 0]));
  const adj = new Map(vertices.map(v => [v, []]));
  for (const [u, v] of edges) {
    adj.get(u).push(v);
    indegree.set(v, (indegree.get(v) || 0) + 1);
  }
  const queue = [];
  for (const v of vertices) if (indegree.get(v) === 0) queue.push(v);
  const order = [];
  while (queue.length) {
    const u = queue.shift();
    order.push(u);
    for (const w of adj.get(u)) {
      indegree.set(w, indegree.get(w) - 1);
      if (indegree.get(w) === 0) queue.push(w);
    }
  }
  if (order.length !== vertices.length) throw new Error('Graph has a cycle');
  return order;
}

// =============== 去重/分组/洗牌 =================
/*
  uniqueArray 说明（最原生）：
  - 基础类型：使用对象 seen 作为哈希集合记录已出现元素。
  - 对象：传入 keySelector 以对象属性或自定义键去重。
*/
function uniqueArray(arr, keySelector) { // 数组去重
  if (typeof keySelector !== 'function') { // 基础类型去重
    var seen = {}; // 记录已出现元素
    var result = []; // 结果数组
    for (var i = 0; i < arr.length; i++) { // 遍历数组
      var value = arr[i]; // 当前值
      var key = String(value); // 将值转为字符串键
      if (!Object.prototype.hasOwnProperty.call(seen, key)) { // 未出现过
        seen[key] = true; // 标记出现
        result.push(value); // 放入结果
      }
    }
    return result; // 返回结果
  }
  var seenKey = {}; // 对象键的集合
  var result2 = []; // 结果数组
  for (var j = 0; j < arr.length; j++) { // 遍历数组
    var item = arr[j]; // 当前元素
    var k = keySelector(item); // 选择用于去重的键
    var kStr = String(k); // 转为字符串键
    if (!Object.prototype.hasOwnProperty.call(seenKey, kStr)) { // 未出现过
      seenKey[kStr] = true; // 标记出现
      result2.push(item); // 放入结果
    }
  }
  return result2; // 返回结果
}

/*
  groupBy 说明（最原生）：
  - 使用对象 {key: 数组} 将元素按照 key 进行分组。
*/
function groupBy(arr, keySelector) { // 分组
  var groups = {}; // key -> 元素数组
  for (var i = 0; i < arr.length; i++) { // 遍历数组
    var item = arr[i]; // 当前元素
    var key; // 组键
    if (typeof keySelector === 'function') { // 函数选择键
      key = keySelector(item); // 计算键
    } else { // 属性名选择键
      key = item[keySelector]; // 读取属性值作为键
    }
    var k = String(key); // 将键转为字符串
    if (!groups[k]) groups[k] = []; // 若无分组则初始化
    groups[k].push(item); // 放入对应分组
  }
  return groups; // 返回分组对象
}

/*
  洗牌算法说明（Fisher–Yates）：
  - 从后向前遍历，每次随机选择 [0,i] 的索引交换。
*/
function shuffle(arr) { // 打乱数组，返回新数组
  var a = arr.slice(0); // 拷贝输入
  for (var i = a.length - 1; i > 0; i--) { // 从后向前遍历
    var j = Math.floor(Math.random() * (i + 1)); // 生成 [0, i] 的随机索引
    var t = a[i]; // 暂存 a[i]
    a[i] = a[j]; // 交换 a[i] 与 a[j]
    a[j] = t; // 放回暂存
  }
  return a; // 返回新数组
}

// =============== 导出（可选） =================
// 为便于复用，如需在其他文件引入，可使用如下导出
if (typeof module !== 'undefined' && module.exports) {
  module.exports = {
    arrayToTree,
    flattenArray,
    deepClone,
    deepEqual,
    dfsTraverseTree,
    bfsTraverseTree,
    binarySearch,
    quickSort,
    mergeSort,
    bubbleSort,
    lengthOfLongestSubstring,
    minSubArrayLen,
    ListNode,
    reverseList,
    twoSum,
    LRUCache,
    debounce,
    throttle,
    curry,
    compose,
    promiseAll,
    promiseAllSettled,
    promiseRace,
    promiseAny,
    EventEmitter,
    pLimit,
    preorder,
    inorder,
    postorder,
    topologicalSort,
    uniqueArray,
    groupBy,
    shuffle
  };
}


